package org.example;

import java.util.*;

// 【练习】栈的经典习题
// https://labuladong.online/algo/problem-set/stack/
public class Stack2 {
    // 考察先进后出性质
    // 对于栈这种数据结构的考察，主要考察先进后出特点的运用，比如表达式运算、括号合法性检测等问题，下面列出几个使用栈的经典场景。

    // 71. 简化路径 【重要案例】
    // 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
    // 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；
    // 两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。
    // 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
    // 请注意，返回的 规范路径 必须遵循下述格式：
    // - 始终以斜杠 '/' 开头。
    // - 两个目录名之间必须只有一个斜杠 '/' 。
    // - 最后一个目录名（如果存在）不能 以 '/' 结尾。
    // - 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
    // 返回简化后得到的 规范路径 。

    // 示例 1：
    // 输入：path = "/home/"
    // 输出："/home"
    // 解释：注意，最后一个目录名后面没有斜杠。
    // 示例 2：
    // 输入：path = "/../"
    // 输出："/"
    // 解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。
    // 示例 3：
    // 输入：path = "/home//foo/"
    // 输出："/home/foo"
    // 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
    // 示例 4：
    // 输入：path = "/a/./b/../../c/"
    // 输出："/c"
    static class SimplifyPath {
        public String simplifyPath(String path) {
            String[] parts = path.split("/");
            Stack<String> stack = new Stack<>();
            // 借助栈计算最终的文件夹路径
            for (String part : parts) {
                if (part.isEmpty() || part.equals(".")) {
                    continue;
                }
                if (part.equals("..")) {
                    if (!stack.isEmpty()) {
                        stack.pop();
                    }
                    continue;
                }
                stack.push(part);
            }
            // 栈中存储的文件夹组成路径
            String res = "";
            while (!stack.isEmpty()) {
                res = "/" + stack.pop() + res;
            }
            return res.isEmpty() ? "/" : res;
        }
    }

    // 150. 逆波兰表达式求值
    // https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
    // 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
    // 请你计算该表达式。返回一个表示表达式值的整数。
    // 注意：
    // 有效的算符为 '+'、'-'、'*' 和 '/' 。
    // 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
    // 两个整数之间的除法总是 向零截断 。
    // 表达式中不含除零运算。
    // 输入是一个根据逆波兰表示法表示的算术表达式。
    // 答案及所有中间计算结果可以用 32 位 整数表示。
    // 示例 1：
    // 输入：tokens = ["2","1","+","3","*"]
    // 输出：9
    // 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
    // 示例 2：
    // 输入：tokens = ["4","13","5","/","+"]
    // 输出：6
    // 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
    // 示例 3：
    // 输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
    // 输出：22
    // 解释：该算式转化为常见的中缀算术表达式为：
    //   ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
    // = ((10 * (6 / (12 * -11))) + 17) + 5
    // = ((10 * (6 / -132)) + 17) + 5
    // = ((10 * 0) + 17) + 5
    // = (0 + 17) + 5
    // = 17 + 5
    // = 22

    // 逆波兰表达式：
    // 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
    // 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
    // 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
    // 逆波兰表达式主要有以下两个优点：
    // 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
    // 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

    // 基本思路
    // 逆波兰表达式发明出来就是为了方便计算机运用[栈]进行表达式运算的，其运算规则如下：
    // 按顺序遍历逆波兰表达式中的字符，如果是数字，则放入栈；如果是运算符，则将栈顶的两个元素拿出来进行运算，再将结果放入栈。对于减法和除法，运算顺序别搞反了，栈顶第二个数是被除（减）数。
    static class EvalRPN {
        public int evalRPN(String[] tokens) {
            Stack<Integer> stk = new Stack<>();
            for (String token : tokens) {
                if ("+-*/".contains(token)) {
                    // 是个运算符，从栈顶拿出两个数字进行运算，运算结果入栈
                    int a = stk.pop();
                    int b = stk.pop();
                    switch (token) {
                        case "+":
                            stk.push(a + b);
                            break;
                        case "*":
                            stk.push(a * b);
                            break;
                        // 对于减法和除法，顺序别搞反了，第二个是被除（减）数
                        case "-":
                            stk.push(b - a);
                            break;
                        case "/":
                            stk.push(b / a);
                            break;
                    }
                } else {
                    // 是个数字，直接入栈即可
                    stk.push(Integer.parseInt(token));
                }
            }
            // 最后栈中剩下一个数字，即是计算结果
            return stk.pop();
        }
    }
    // 225. 用队列实现栈
    // 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
    // 实现 MyStack 类：
    // void push(int x) 将元素 x 压入栈顶。
    // int pop() 移除并返回栈顶元素。
    // int top() 返回栈顶元素。
    // boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
    // 注意：
    // 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
    // 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
    // 示例：
    // 输入：
    // ["MyStack", "push", "push", "top", "pop", "empty"]
    // [[], [1], [2], [], [], []]
    // 输出：
    // [null, null, null, 2, 2, false]
    // 解释：
    // MyStack myStack = new MyStack();
    // myStack.push(1);
    // myStack.push(2);
    // myStack.top(); // 返回 2
    // myStack.pop(); // 返回 2
    // myStack.empty(); // 返回 False
    static class MyStack{
        Queue<Integer> q = new LinkedList<>();
        int top_elem = 0;
        public MyStack() {

        }

        // 将元素x压入栈顶
        public void push(int x) {
            // x是队列的队尾，是栈的栈顶
            q.offer(x);
            top_elem = x;
        }
        // 删除栈顶的元素并返回
        // 实现原理
        // 在这个实现中：
        // 队列的队尾元素相当于栈顶元素
        // 为了移除队尾元素（栈顶），需要先将前面的元素循环移动到队尾
        // 当只剩下最后两个元素时，执行特殊操作
        public int pop() {
            int size = q.size();
            // 留下队尾2个元素
            // size>2的原理
            // 这样做的目的是：
            // 保留最后两个元素
            // 将倒数第二个元素（新的栈顶）记录到 top_elem 变量
            // 然后将这个新的栈顶元素移回队尾
            // 最后移除并返回原来的队尾元素（栈顶）
            while(size > 2){
                q.offer(q.poll());
                size--;
            }
            // 记录新的队尾元素
            top_elem = q.peek();
            q.offer(q.poll());
            // 删除之前的队尾元素
            return q.poll();
        }

        // 返回栈顶元素
        public int top() {
            return top_elem;
        }

        public boolean empty() {
            return q.isEmpty();
        }
        public static void main(String[] args) {
            new SimplifyPath().simplifyPath("/.../a/../b/c/../d/./");
        }
    }



    // 388. 文件的最长绝对路径
    // https://leetcode.cn/problems/longest-absolute-file-path/description/
    // 给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中 指向 【文件】 的 【最长绝对路径】 的长度 。 如果系统中没有文件，返回 0。
    // 输入：input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
    // 输出：32
    // 解释：存在两个文件：
    // "dir/subdir1/file1.ext" ，路径长度 21
    // "dir/subdir2/subsubdir2/file2.ext" ，路径长度 32
    //返回 32 ，因为这是最长的路径
    static class LengthLongestPath {
        public int lengthLongestPath(String input) {
            // 这个栈存储之前的父路径。实际上这里只用存父路径的长度就够了，这个优化留给你吧
            Deque<String> stack = new LinkedList<>();
            int maxLen = 0;
            for(String part : input.split("\n")){
                // lastIndexOf ("\t") 的含义：lastIndexOf("\t") 方法返回字符串中最后一个制表符 \t 的索引位置。如果字符串中没有制表符，则返回 -1。
                int level = part.lastIndexOf("\t") + 1;
                // 调整栈的大小，确保栈中只保留当前目录的父路径
                // 如果当前层级小于栈的大小，说明需要弹出上层目录
                while(level < stack.size()){
                    stack.removeLast();
                }
                // 将当前文件/目录名（去除制表符）添加到栈中
                stack.addLast(part.substring(level));
                // 如果是文件，就计算路径长度
                // 如果当前部分包含"."，说明是一个文件
                if (part.contains(".")){
                    // 计算当前文件的完整路径长度
                    int sum = stack.stream().mapToInt(String::length).sum();
                    // 加上路径分隔符"/"的数量（比目录数量少1）
                    sum+=stack.size()-1;
                    // 更新最大路径长度
                    maxLen = Math.max(maxLen, sum);
                }
            }
            return maxLen;
        }

        public static void main(String[] args) {
            new LengthLongestPath().lengthLongestPath("dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext");
        }
    }
    // 155. 最小栈
    // 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    // 实现 MinStack 类:
    // MinStack() 初始化堆栈对象。
    // void push(int val) 将元素val推入堆栈。
    // void pop() 删除堆栈顶部的元素。
    // int top() 获取堆栈顶部的元素。
    // int getMin() 获取堆栈中的最小元素。
    // 示例 1:
    // 输入：
    // ["MinStack","push","push","push","getMin","pop","top","getMin"]
    // [[],[-2],[0],[-3],[],[],[],[]]
    // 输出：
    // [null,null,null,null,-3,null,0,-2]
    // 解释：
    // MinStack minStack = new MinStack();
    // minStack.push(-2);
    // minStack.push(0);
    // minStack.push(-3);
    // minStack.getMin();   --> 返回 -3.
    // minStack.pop();
    // minStack.top();      --> 返回 0.
    // minStack.getMin();   --> 返回 -2.
    static class MinStack{
        // 记录栈中的所有元素
        Stack<Integer> stk = new Stack<>();
        // 阶段性记录栈中的最小元素
        Stack<Integer> minStk = new Stack<>();

        public MinStack() {

        }

        public void push(int val) {
            stk.push(val);
            // 维护minStk栈顶为全栈最小元素
            if (minStk.isEmpty() || val <= minStk.peek()){
                // 新插入的这个元素就是全栈最小的
                minStk.push(val);
            }
        }

        public void pop() {
            // 注意Java的语言特性，比较Integer相等要用equals方法
            if (stk.peek().equals(minStk.peek())){
                // 弹出的元素是全栈最小的
                minStk.pop();
            }
            stk.pop();
        }

        public int top() {
            return stk.peek();
        }

        public int getMin() {
            // minStk栈顶为全栈最小元素
            return minStk.peek();
        }
    }

    // 895. 最大频率栈
    // 设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
    // 实现 FreqStack 类:
    // FreqStack() 构造一个空的堆栈。
    // void push(int val) 将一个整数 val 压入栈顶。
    // int pop() 删除并返回堆栈中出现频率最高的元素。
    // 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。
    // 示例 1：
    // 输入：
    // ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
    // [[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
    // 输出：[null,null,null,null,null,null,null,5,7,5,4]
    // 解释：
    // FreqStack = new FreqStack();
    // freqStack.push (5);//堆栈为 [5]
    // freqStack.push (7);//堆栈是 [5,7]
    // freqStack.push (5);//堆栈是 [5,7,5]
    // freqStack.push (7);//堆栈是 [5,7,5,7]
    // freqStack.push (4);//堆栈是 [5,7,5,7,4]
    // freqStack.push (5);//堆栈是 [5,7,5,7,4,5]
    // freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。
    // freqStack.pop ();//返回 7 ，因为 5 和 7 出现频率最高，但7最接近顶部。堆栈变成 [5,7,5,4]。
    // freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,4]。
    // freqStack.pop ();//返回 4 ，因为 4, 5 和 7 出现频率最高，但 4 是最接近顶部的。堆栈变成 [5,7]。
    static class FreqStack {
        // 记录FreqStack中元素的最大频率
        int maxFreq = 0;
        // 记录FreqStack中每个val对应的出现频率，后文称为VF表
        HashMap<Integer, Integer> valTpFreq = new HashMap<>();
        // 记录频率freq对应的val列表，后文就称为FV表
        HashMap<Integer, Stack<Integer>> freqToVals = new HashMap<>();

        public FreqStack() {

        }

        public void push(int val) {
            // 修改VF表：val对应的freq加1
            int freq = valTpFreq.getOrDefault(val, 0) + 1;
            valTpFreq.put(val, freq);
            // 修改FV表：在freq对应的列表加上val
            freqToVals.putIfAbsent(freq, new Stack<>());
            freqToVals.get(freq).push(val);
            // 更新maxFreq
            maxFreq = Math.max(maxFreq, freq);
        }

        public int pop() {
            // 修改FV表：pop出一个maxFreq对应的元素v
            Stack<Integer> vals = freqToVals.get(maxFreq);
            int v = vals.pop();
            // 修改VF表：v对应的freq减1
            int freq = valTpFreq.get(v)-1;
            valTpFreq.put(v, freq);
            // 更新maxFreq
            if (vals.isEmpty()){
                // 如果maxFreq对应的元素空了
                maxFreq--;
            }
            return v;
        }
    }
}
